﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0029_Merge : IAlgorithm
    {
        // 合并两个有序数组

        // 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

        // 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

        // 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，
        // 后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

        // 提示：
        //  nums1.length == m + n
        //  nums2.length == n
        //  0 <= m, n <= 200
        //  1 <= m + n <= 200
        //  -10^9 <= nums1[i], nums2[j] <= 10^9

        // 进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？


        public void Test()
        {
            // 算法参数定义
            //var nums1 = new int[] { 1, 2, 3, 0, 0, 0 };
            //var m = 3;
            //var nums2 = new int[] { 2, 5, 6 };
            //var n = 3;
            var nums1 = new int[] { 2, 0 };
            var m = 1;
            var nums2 = new int[] { 1 };
            var n = 1;
            // 算法执行与打印
            Merge(nums1, m, nums2, n);
            for (int i = 0; i < nums1.Length; i++)
            {
                Console.WriteLine(nums1[i]);
            }
        }

        // 算法
        // 挺简单的，数组1必然长度等于m+n，同时二者均是非递减，所以两个数组从后向前循环取大值放置最后一位即可
        public void Merge(int[] nums1, int m, int[] nums2, int n)
        {
            m--; n--;
            int i = nums1.Length - 1;
            // 数组2若取完，剩下的数组1已是非递减，可直接返回
            while (n >= 0)
                nums1[i--] = m >= 0 && nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
        }
    }
}
